package com.offer.arr;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-12-08 16:22
 * @version: 1.0
 * @description: 数组一些列问题
 **/
public class CaseOne {

    /**
     * 数组中重复的数字   剑指 Offer 03
     * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
     * 数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
     * 请找出数组中任意一个重复的数字。
     * @param nums
     * @return
     */
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            if(nums[i] == i) {
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i]) return nums[i];
            int tmp = nums[i];
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }
        return -1;
    }

    /**
     * 剑指 Offer 53 - I. 在排序数组中查找数字
     * 统计一个数字在排序数组中出现的次数。
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        if(nums.length == 0) return 0;
        int start = findFirstIndex(nums,target);
        if (start == -1) return 0;
        int end = findLastIndex(nums,target);
        return end - start + 1;
    }

    private int findLastIndex(int[] nums, int target) {
        int left = 0,right = nums.length - 1;
        while(left < right){
//			int mid = (low + high) / 2;
            int mid = left + (right - left + 1) / 2; // 防止int值越界
            if (target == nums[mid]){
                left = mid;
            }else if (target < nums[mid]){
                right = mid - 1 ;
            }else if(target > nums[mid]){
                left = mid + 1;
            }
        }
        return right;
    }

    private int findFirstIndex(int[] nums, int target) {
        int left = 0,right = nums.length - 1;
        while(left < right){
//			int mid = (low + high) / 2;
            int mid = left + (right - left) / 2; // 防止int值越界
            if (target == nums[mid]){
                right = mid;
            }else if (target < nums[mid]){
                right = mid - 1 ;
            }else if(target > nums[mid]){
                left = mid + 1;
            }
        }
        if (nums[left] == target) return left;
        return -1;
    }


    /**
     * 0～n-1中缺失的数字
     * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
     * 在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {
        int left = 0,right = nums.length - 1;
        while (left <= right){
            int mid = left + (right - left)/2;
            if (mid == nums[mid]){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }

        return left;

    }

    public static void main(String[] args) {
        CaseOne co = new CaseOne();
        co.missingNumber(new int[]{0,1,3,4,5});
    }
}
